#include <iostream>
#include <vector>

void printResult(std::string test_name, bool found, bool not_found) {
    std::cout << test_name << " found: " << found
        << "; not_found: " << not_found << std::endl;
}
// 顺序查找，不写了

// 二分查找（循环），用>>1是因为右移运算符比除法快
// 不用mid = (left + right) >> 1是因为left + right可能溢出
bool binarySearchWhile(const std::vector<int> &input, int val) {
    int left = 0;
    int right = input.size() - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (input[mid] == val) {
            return true;
        }
        if (input[mid] < val) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

// 二分查找（递归）
bool binarySearchCore(const std::vector<int> &input, int val, int left, int right) {
    if (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (input[mid] == val) {
            return true;
        }
        if (input[mid] < val) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        return binarySearchCore(input, val, left, right);
    }
    return false;
}

bool binarySearchRecurisive(const std::vector<int> &input, int val) {
    return binarySearchCore(input, val, 0, input.size() - 1);
}

// 插值查找，与二分查找相似，把mid的计算方式改为：
// mid = left + (val - input[left]) / (input[right] - input[left]) * (right - left)

// 斐波那契查找，mid根据斐波那契数列计算
// 查找长度必须是fibonacci(k) - 1，不够用最后一个数填满
int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

void getFibonacci(std::vector<int> &fb, int n) {
    fb.push_back(0);
    fb.push_back(1);
    for (int i = 2; i <= n; i++) {
        fb.push_back(fb[i - 1] + fb[i - 2]);
    }
}

bool fibonacciSearchWhile(std::vector<int> &input, int val) {
    if (input.empty()) {
        return false;
    }
    int k = 0;
    int size = input.size();
    while (size > fibonacci(k) - 1) {
        k++;
    }
    std::vector<int> fb;
    getFibonacci(fb, k);
    while (input.size() < fibonacci(k) - 1) {
        input.push_back(input.back());
    }
    int left = 0;
    int right = input.size() - 1;
    while (left <= right) {
        int mid = left + fb[k - 1] - 1;
        if (input[mid] == val) {
            return true;
        } else if (input[mid] < val) {
            left = mid + 1;
            k = k - 2;
        } else {
            right = mid - 1;
            k = k - 1;
        }
    }
    return false;
}

// 斐波那契查找（递归），和循环写法一个道理
bool ficonacciSearchCore(const std::vector<int> &input, int val,
        const std::vector<int> &fb, int left, int right, int k) {
    if (val < input[left] || val > input[right] || left > right) {
        return false;
    }

    int mid = left + fb[k - 1] - 1;
    if (input[mid] == val) {
        return true;
    } else if (input[mid] < val) {
        left = mid + 1;
        k = k - 2;
    } else {
        right = mid - 1;
        k = k - 1;
    }
    return ficonacciSearchCore(input, val, fb, left, right, k);
}

bool fibonacciSearchRecurisive(std::vector<int> &input, int val) {
    if (input.empty()) {
        return false;
    }
    int k = 0;
    int size = input.size();
    while (size > fibonacci(k) - 1) {
        k++;
    }
    std::vector<int> fb;
    getFibonacci(fb, k);
    while (input.size() < fibonacci(k) - 1) {
        input.push_back(input.back());
    }
    int left = 0;
    int right = input.size() - 1;
    return ficonacciSearchCore(input, val, fb, left, right, k);
}

// 分块查找，不要求输入全部有序，只需每个块内是有序的
// index是每个块内的最大值（有序）
// val是要查找的值
// 返回在index中第一个大于val的索引
int blockSearchCore(const std::vector<int> &index, int val) {
    int left = 0;
    int right = index.size() - 1;
    if (index[right] < val) {
        return -1;
    }
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (index[mid] >= val) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// index: 每个块内的最大值（有序）
// input: 要查找的数组
// val: 要查找的元素
// block: 块大小
bool blockSearch(const std::vector<int> &index,
                 const std::vector<int> &input,
                 int val,
                 int block) {
    int idx = blockSearchCore(index, val);
    if (idx < 0) {
        return false;
    }
    for (int i = idx * block; i < idx * block + block; i++) {
        if (input[i] == val) {
            return true;
        }
    }
    return false;
}

// 哈希查找，主要是构造哈希值和解决冲突
// 构造哈希
void buildHash(std::vector<int> &hash, int val) {
    int index = val % hash.size();
    while (hash[index] != 0) {
        index = (++index) % hash.size();
    }
    hash[index] = val;
}

bool hashSearch(std::vector<int> &hash, int val) {
    int index = val % hash.size();
    while (hash[index] != 0 && hash[index] != val) {
        index = (++index) % hash.size();
    }
    if (hash[index] == 0) {
        return false;
    }
    return true;
}

int main() {
    std::vector<int> input = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    bool found = binarySearchWhile(input, 4);
    bool not_found = binarySearchWhile(input, 10);
    printResult("[binarySearchWhile]", found, not_found);

    found = binarySearchRecurisive(input, 4);
    not_found = binarySearchRecurisive(input, 10);
    printResult("[binarySearchRecurisive]", found, not_found);

    found = fibonacciSearchWhile(input, 4);
    not_found = fibonacciSearchWhile(input, 10);
    printResult("[fibonacciSearchWhile]", found, not_found);

    found = fibonacciSearchRecurisive(input, 4);
    not_found = fibonacciSearchRecurisive(input, 10);
    printResult("[fibonacciSearchRecurisive]", found, not_found);

    std::vector<int> index = {22, 48, 86};
    input = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53};
    found = blockSearch(index, input, 42, 6);
    not_found = blockSearch(index, input, 28, 6);
    printResult("[blockSearch]", found, not_found);

    input = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53};
    std::vector<int> hash(input.size() + 1, 0);
    for (int i = 0; i < input.size(); i++) {
        buildHash(hash, input[i]);
    }
    found = hashSearch(hash, 42);
    not_found = hashSearch(hash, 28);
    printResult("[hashSearch]", found, not_found);

    return 0;
}
